// 题目描述
// 86. 分隔链表
// 难度
// 中等
// 733
// 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
// 你应当 保留 两个分区中每个节点的初始相对位置。
//   示例 1：
// 输入：head = [1,4,3,2,5,2], x = 3
// 输出：[1,2,2,4,3,5]
// 示例 2：
// 输入：head = [2,1], x = 2
// 输出：[1,2]
//   提示：
// 链表中节点的数目在范围 [0, 200] 内
// -100 <= Node.val <= 100
// -200 <= x <= 200
// 通过次数224,711提交次数349,904
// https://leetcode.cn/problems/partition-list/

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

/**
 * @param {ListNode} head
 * @param {number} x
 * @return {ListNode}
 */
var partition = function (head, x) {
  // 固定套路先创建哨兵节点
  let dummy1 = new ListNode('#1'), tail1 = dummy1
  let dummy2 = new ListNode('#2'), tail2 = dummy2

  // 一个链表拆分为两个链表
  let p = head
  while (null !== p) {
    const cloned = p
    p = p.next

    if (cloned.val < x) {
      tail1.next = cloned
      tail1 = cloned
    } else {
      tail2.next = cloned
      tail2 = cloned
    }
  }

  // 清除链表尾部
  tail1.next = dummy2.next
  tail2.next = null

  // 清除哨兵节点
  return dummy1.next
}

const list = new ListNode(1, new ListNode(4, new ListNode(3, new ListNode(2, new ListNode(5, new ListNode(2))))))
console.log(
  partition(
    list,
    3
  )
)
